#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 定义二叉树的节点
struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 定义队列节点
struct QueueNode
{
    struct TreeNode *node;
    struct QueueNode *next;
};

// 定义队列
struct Queue
{
    struct QueueNode *head;
    struct QueueNode *rear;
};

// 创建二叉树节点
struct TreeNode *newTreeNode(int val)
{
    struct TreeNode *newNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

// 创建队列的节点
struct QueueNode *newQueueNode(struct TreeNode *node)
{
    struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));

    newNode->node = node;
    newNode->next = NULL;

    return newNode;
}

// 创建队列
struct Queue *createQueue()
{
    struct Queue *newQueue = (struct Queue *)malloc(sizeof(struct Queue));
    newQueue->head = NULL;
    newQueue->rear = NULL;
}

// 入队操作
void enqueue(struct Queue *queue, struct TreeNode *node)
{
    struct Queue * qnode = newQueueNode(node);
    if(queue->rear == NULL)
    {
        queue->head = qnode;
        queue->rear = qnode;
    }
    queue->rear->next = qnode;
    queue->rear = qnode;
}

// 出队操作
struct TreeNode *dequeue(struct Queue *queue)
{
    if(queue->head = NULL)
    {
        return NULL;
    }

    struct TreeNode *node = queue->head->node;
    struct QueueNode *tmp = queue->head;

    queue->head = queue->head->next;
    if(queue->head == NULL)
    {
        queue->rear = NULL;
    }

    free(tmp);
    return node;
}

// 队列是否为空
bool isQueueEmpty(struct Queue *queue)
{
    return queue->head == NULL;
}

// 判断是否是完全二叉树
bool isTree(struct TreeNode *root)
{
    if(root == NULL)
    {
        return true;
    }

    struct Queue *queue = creatQueue(); // 创建一个队列

    bool flag = false;
    enqueue(queue, root);

    while(isQueueEmpty(queue))
    {
        struct TreeNode *currentNode = dequeue(queue->head);
        // 检查左孩子
        if(currentNode->left)
        {
            if(flag)
            {

            }
        }
    }
}